#include <stdio.h>
#include <assert.h>
#include <fcntl.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <unistd.h>
#include <assert.h>
#include <string.h>
#include <sys/mman.h>
#include <stdlib.h>

#include "inner.h"

typedef uint32_t ckid_t;    // chunk_id
typedef uint32_t lpid_t;    // local page id
#define NULL_CK    ((uint64_t)(-1L))

// 分配器
struct allocator_s {
    // 当前 chunk_id
    ckid_t curr_ck;
    // 记录每个 chunk 中,所使用的 page 数量, chunk 默认是2GB大小, 最多 512K 个 page 数量
    // 最多 256K 个 chunk; 262,144 * 4B = 1MB
    struct busy_page_num_s *bpn;
    // 每一个 chunk 头的 bitmap, 统计每个 page 的 是否使用了的情况. 0 or 1
    // 使用的是 位bit 表示法
    struct page_bitmap_s *pb;
};

// 文件分配
void file_allocate(kvdb_t db, uint64_t pos, uint64_t len) {
    struct file_header_s *h = db->h;
    int ret;

    if (h->file_size >= pos + len) {
        return;
    }
    // 文件分配
    ret = posix_fallocate(db->fd, pos, len);
    kvdb_assert(ret == 0);
    h->file_size = pos + len;
}

/* find a chunk which has free pages to allocate */
static ckid_t find_ck(kvdb_t db, ckid_t ck) {
    ckid_t i, r;
    struct allocator_s *alc = db->alc;
    // 从 0 到 262,144 ，遍历每个 chunk
    for (i = 0; i < MAX_CHUNK_NUM; i++) {
        // 从当前 chunk_id 开始判断，有可能当前 chunk 满了，那么就顺序向后找
        r = (ck + i) % MAX_CHUNK_NUM;
        // 每个 chunk 最多放 524,288 个 page
        // 第 i 个 chunk 的 page_num 值 是否 < 524,288 个
        if (alc->bpn->n[i] < PAGE_NUM_PER_CK) {
            return r;
        }
    }
    return (ckid_t) -1;
}

// 当前页的 首地址
uint64_t get_page_pos(gpid_t gpid) {
    // 2MB + gp id * 4KB
    return (FILE_META_LEN + gpid * PAGE_SIZE);
}

// 获得全局唯一 page_id
static gpid_t get_gpid(ckid_t ck, lpid_t lpid) {
    // 第几个 chunkID * 524,288 个 +
    // ckid * 524,288 个 + local page id
    return (((gpid_t) ck) * PAGE_NUM_PER_CK + lpid);
}

// 获得 当前 chunk 中的当前 page 的首地址
uint64_t get_ck_pos(ckid_t ck) {
    gpid_t gpid;
    uint64_t offset;
    // chunk_id + page_id
    gpid = get_gpid(ck, 0);
    // 获得 当前 chunk 中的当前 page 的首地址
    offset = get_page_pos(gpid);
    return offset;
}

static void close_curr_ck(kvdb_t db) {
    struct allocator_s *alc = db->alc;
    int ret;

    kvdb_assert(alc->curr_ck != (ckid_t) -1);
    kvdb_assert(alc->pb != NULL);

    ret = msync(alc->pb, PAGE_BITMAP_LEN, MS_SYNC);
    kvdb_assert(ret == 0);

    ret = munmap(alc->pb, PAGE_BITMAP_LEN);
    kvdb_assert(ret == 0);

    alc->curr_ck = (ckid_t) -1;
    alc->pb = NULL;
}

// local page id
// 判断传入的 page 是否使用了？
static int pb_isset(kvdb_t db, lpid_t pg) {
    // 无符号32位 右移6位 = pg 高26位 => 当前id ➗ 64 = 数组的索引值 => 第几组
    uint32_t w = pg >> 6;
    // 无符号32位 & 0011 1111 = pg 低6位 => pg%64 pg&63 =>  组中第几个 id 值
    uint32_t b = pg & 63;// b 最大是 63 ，0-63 号
    // x 相当于管理 64 个 4KB 块，此时获得当前组的 bitmap
    uint64_t x = db->alc->pb->w[w];
    // 自己所在的槽
    uint64_t y = 1 << b;
    // 判断 入参时的槽位 是否 被占用了
    return (x & y) != 0;
}

// page bit map set 1
static void pb_set(kvdb_t db, lpid_t pg) {
    uint32_t w = pg >> 6;// 第几组
    uint32_t b = pg & 63;// 组中第几个

    db->alc->pb->w[w] |= (1 << b);
}

static void pb_clr(kvdb_t db, lpid_t pg) {
    uint32_t w = pg >> 6;
    uint32_t b = pg & 63;
    // bitmap 的位置置为 0 ，说明此处页 未被使用
    db->alc->pb->w[w] &= ~(1 << b);
}

/* 
 * open_ck() -- load a page bitmap into memory. At any moment, there is only 
 * 				one ck could be staying in the memory to provide free pages.
 * 				在任何时候, 只有一个ck可以留在内存中以提供免费页面
 */
static void open_ck(kvdb_t db, ckid_t ck) {
    uint64_t offset; //
    struct allocator_s *alc = db->alc;
    int new = 0;
    lpid_t i;

    kvdb_assert(alc->curr_ck == (ckid_t) -1);
    kvdb_assert(ck != (ckid_t) -1);

    // 分配器保存当前的 chunk id
    alc->curr_ck = ck;
    // 获得当前 chunk 中的当前首个 page 的首地址
    offset = get_ck_pos(ck);
    // 等于 0 说明，没有 page 被分配，可以继续分配
    if (alc->bpn->n[ck] == 0) {
        // 文件开拓太小，继续加大
        if (db->h->file_size < offset + PAGE_BITMAP_LEN) {
            // 继续扩大 64KB
            file_allocate(db, offset, PAGE_BITMAP_LEN);
        }
        new = 1;
    }

    alc->pb = mmap(NULL, sizeof(struct page_bitmap_s),
                   PROT_READ | PROT_WRITE, MAP_SHARED,
                   db->fd, offset);
    kvdb_assert(alc->bpn != MAP_FAILED);
    // 是否 文件扩容了
    if (new) {
        // 将当前 chunk 的 page 数量初始化为16个
        alc->bpn->n[ck] = PAGE_BITMAP_PAGES;
        // 将16个 page 都设置为 使用中
        for (i = 0; i < PAGE_BITMAP_PAGES; i++) {
            // db->alc->pb->w[w] |= (1 << b);
            pb_set(db, i);
        }
    }
    // 没有文件扩容 直接返回
}

// 分配新page页面
gpid_t alloc_page(kvdb_t db) {
    struct allocator_s *alc = db->alc;
    ckid_t ck = alc->curr_ck;
    lpid_t lpid;
    gpid_t gpid;
    uint64_t pos;

    kvdb_assert(ck != (ckid_t) -1);

    /*
     * If there is not any free page in the chunk, then we find the next one and turn to it */
    // 当前chunk中的page数量 > 524,288 个，说明需要找下一个chunk
    if (alc->bpn->n[ck] >= PAGE_NUM_PER_CK) {
        close_curr_ck(db);
        // 查找下一个 chunk
        ck = find_ck(db, ck);
        // 当到达最大长度时，需要解决这个问题
        /* TODO: reach the maximum length of the file, need to deal with it */
        kvdb_assert(ck != (ckid_t) -1);
        // 在任何时候，只有一个ck可以留在内存中以提供免费页面
        open_ck(db, ck);
    }

    /* Find a free page in the chunk */
    // 从 16 开始，524,288 结束
    for (lpid = PAGE_BITMAP_PAGES; lpid < PAGE_NUM_PER_CK; lpid++) {
        // 获得全局唯一 page id
        gpid = get_gpid(ck, lpid);
        // 如果当前 page 没有被使用，那么就返回
        if (!pb_isset(db, gpid)) {
            break;
        }
    }

    kvdb_assert(lpid < PAGE_NUM_PER_CK);
    // 标记当前 page 使用了
    pb_set(db, gpid);
    // chunk所记录的page数量++
    alc->bpn->n[ck]++;
    // 获得新 page 的首地址
    pos = get_page_pos(gpid);
    // 再次判断文件大小是否满足 存储要求
    if (db->h->file_size < pos + PAGE_SIZE) {
        file_allocate(db, pos, PAGE_SIZE);
    }
    return gpid;
}

void free_page(kvdb_t db, gpid_t gpid) {
    // 获得 chunk id
    ckid_t ck = (ckid_t) (gpid / PAGE_NUM_PER_CK);

    kvdb_assert(pb_isset(db, gpid));
    // page_bitmap 相关索引处置空
    pb_clr(db, gpid);
    // ck 中 page 的数量 --
    db->alc->bpn->n[ck]--;
    db->h->spare_pages++;
    /* TODO: truncate those free pages at the tail of the database file */
    // 截断数据库文件尾部的那些可用页
    /* TODO: Do we need to implement some GC things? */
}

void sync_allocator(kvdb_t db) {
    int ret;

    if (db->alc->pb != NULL) {
        // 将bitmap 刷入磁盘中
        ret = msync(db->alc->pb, PAGE_BITMAP_LEN, MS_SYNC);
        kvdb_assert(ret == 0);
    }

    kvdb_assert(db->alc->bpn != NULL);
    // 将 chunk中的 page nums 信息 刷入磁盘中
    ret = msync(db->alc->bpn, sizeof(struct busy_page_num_s), MS_SYNC);
    kvdb_assert(ret == 0);

}

void exit_allocator(kvdb_t db) {
    int ret;
    // 退出之前 先刷盘
    sync_allocator(db);

    if (db->alc->pb != NULL) {
        // 释放 mmap
        ret = munmap(db->alc->pb, PAGE_BITMAP_LEN);
        kvdb_assert(ret == 0);
        db->alc->curr_ck = (ckid_t) -1;
        db->alc->pb = NULL;
    }
    // 释放 mmap
    ret = munmap(db->alc->bpn, sizeof(struct busy_page_num_s));
    kvdb_assert(ret == 0);
    db->alc->bpn = NULL;
    free(db->alc);
    db->alc = NULL;
}

// 分配器初始化, 加载chunk到内存, 构建chunk索引
void init_allocator(kvdb_t db) {
    struct allocator_s *alc;
    int new = 0;
    ckid_t ck;
    // 分配指针
    alc = (struct allocator_s *) malloc(sizeof(*alc));
    kvdb_assert(alc != NULL);
    // 设置为 0
    memset(alc, 0, sizeof(*alc));

    db->alc = alc;
    alc->curr_ck = (ckid_t) -1;

    /*
     * if the file size smaller than the area of busy page number,
     * the foile is a new one, so it is needed t be expanded.
     */
    // file_size < 1MB位移 + 1MB大小 = 数据文件开始位置
    if (db->h->file_size < BUSY_PAGE_NUM_POS + sizeof(struct busy_page_num_s)) {
        // 说明数据文件太小，需要扩容
        file_allocate(db, BUSY_PAGE_NUM_POS, sizeof(struct busy_page_num_s));
        new = 1;
    }

    // busy_page_num_s 1MB 还用mmap
    alc->bpn = mmap(NULL, sizeof(struct busy_page_num_s),
                    PROT_READ | PROT_WRITE, MAP_SHARED,
                    db->fd, BUSY_PAGE_NUM_POS);
    kvdb_assert(alc->bpn != MAP_FAILED);

    if (new) {
        //全都初始化为 0
        memset(alc->bpn, 0, sizeof(struct busy_page_num_s));
    }
    // 找到第一个 chunk 编号
    ck = find_ck(db, 0);
    kvdb_assert(ck != (ckid_t) -1);
    // 加载到内存中
    open_ck(db, ck);
}

